package botTicTacToe;

/**
 * This class stores information about state of the game
 */
public class GameField implements Cloneable {
	public static final int MARK_NONE = 0;
	public static final int MARK_X = 1;
	public static final int MARK_O = 2;
	
	public static final int WINNER_NONE = 0;
	public static final int WINNER_X = 1;
	public static final int WINNER_O = 2;
	public static final int WINNER_DRAW = WINNER_X + WINNER_O;
	
	public static final int CELL_NUMBER = 9;
	public static final int CELL_NUMBER_X = 3;
	public static final int CELL_NUMBER_Y = 3;
	
	/**
	 * This byte string contains positions of marks <br>
	 * Every space is represented by two bits: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O <br>
	 * Grid is accessed in following order: <br>
	 * 0 1 2 <br>
	 * 3 4 5 <br>
	 * 6 7 8
	 */
	private FieldString field;
	
	//If both variables set then the game ended with draw
	//If none set then the game is not over yet
	private boolean winX;
	private boolean winO;
	
	public GameField() {
		field = new FieldString();
		winX = false;
		winO = false;
	}
	
	/**
	 * Creates object using array of positions as input
	 * @param field - array 3x3 in following format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 */
	public GameField(byte[][] field) {
		this.field = new FieldString();
		for (byte y = 0; y < field.length; y++) {
			byte[] row = field[y];
			for (byte x = 0; x < row.length; x++) {
				this.field.set(y*CELL_NUMBER_X+x, row[x]);
			}
		}
		checkWinner();
	}
	
	/**
	 * @return GameField.WINNER_NONE - Game has not ended yet <br>
	 * GameField.WINNER_X - X wins <br>
	 * GameField.WINNER_O - O wins <br>
	 * GameField.WINNER_DRAW - Draw
	 */
	public byte getWinner() {
		byte winner = WINNER_NONE;
		if (winX) winner += WINNER_X;
		if (winO) winner += WINNER_O;
		return winner;
	}
	
	/**
	 * Attempts to place mark in specified coordinates
	 * this function checks if game is not over and target cell is empty
	 * @param mark format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 * @param x - horizontal coord (0..2)
	 * @param y - vertical coord (0..2)
	 * @return true if mark was placed successfully, false otherwise
	 */
	public boolean placeMark(int mark, int x, int y) {
		if (field.get(y*CELL_NUMBER_X+x) != 0) return false;
		if (isGameEnd()) return false;
		setMark(mark, x, y);
		return true;
	}
	
	/**
	 * Attempts to place mark in cell with specified number
	 * this function checks if game is not over and target cell is empty
	 * @param mark format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 * @param cellN - number of cell on the grid: <br>
	 * 0 1 2 <br>
	 * 3 4 5 <br>
	 * 6 7 8 <br>
	 * @return true if mark was placed successfully, false otherwise
	 */
	public boolean placeMark(int mark, int cellN) {
		if (field.get(cellN) != MARK_NONE) return false;
		if (getWinner() != WINNER_NONE) return false;
		setMark(mark, cellN);
		return true;
	}
	
	/**
	 * Sets mark in specified coordinates
	 * @param mark format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 * @param x - horizontal coord (0..2)
	 * @param y - vertical coord (0..2)
	 */
	public void setMark(int mark, int x, int y) {
		this.field.set(y*CELL_NUMBER_X+x, mark);
		checkWinner();
	}
	
	/**
	 * Sets mark in cell with specified number
	 * @param mark format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 * @param cellN - number of cell on the grid: <br>
	 * 0 1 2 <br>
	 * 3 4 5 <br>
	 * 6 7 8 <br>
	 */
	public void setMark(int mark, int cellN) {
		this.field.set(cellN, mark);
		checkWinner();
	}
	
	/**
	 * @return numbers of empty cells
	 */
	public int[] getEmptyCells() {
		int cardinality = field.cardinality();
		if (cardinality == CELL_NUMBER) return null;
		int[] cells = new int[CELL_NUMBER - cardinality];
		int j = 0;
		for (int i = 0; i < CELL_NUMBER; i++) {
			if (field.get(i) == MARK_NONE) cells[j++] = i;
			if (j == cells.length) break;
		}
		return cells;
	}
	
	/**
	 * Returns mark in cell
	 * @param x - horizontal coord (0..2)
	 * @param y - vertical coord (0..2)
	 * @return GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 */
	public byte getCell(int x, int y) {
		return field.get(y*CELL_NUMBER_X+x);
	}
	
	/**
	 * Returns mark in cell
	 * @param cellN - number of cell on the grid: <br>
	 * 0 1 2 <br>
	 * 3 4 5 <br>
	 * 6 7 8 <br>
	 * @return GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 */
	public byte getCell(int cellN) {
		return field.get(cellN);
	}
	
	/**
	 * @return array 3x3 in following format: <br>
	 * GameField.MARK_NONE - no mark <br>
	 * GameField.MARK_X - X <br>
	 * GameField.MARK_O - O
	 */
	public byte[][] getCellArray() {
		byte[][] fieldArray = new byte[CELL_NUMBER_Y][CELL_NUMBER_X];
		for (byte y = 0; y < CELL_NUMBER_Y; y++) {
			for (byte x = 0; x < CELL_NUMBER_X; x++) {
				fieldArray[y][x] = getCell(x, y);
			}
		}
		return fieldArray;
	}
	
	public GameField clone() throws CloneNotSupportedException {
		GameField newField = (GameField)super.clone();
		newField.field = field.clone();
		return  newField;
	}
	
	/**
	 * This method checks field and sets winner
	 */
	private void checkWinner() {
		//Clear last two bits
		winO = false;
		winX = false;
		//There are total of 8 winning positions:
		byte[][] conditions = {{0, 1, 2},
								 {3, 4, 5},
								 {6, 7, 8},
								 {0, 3, 6},
								 {1, 4, 7},
								 {2, 5, 8},
								 {0, 4, 8},
								 {2, 4, 6}};
		 
		//Check if we have enough turns first
		boolean enoughTurns = false;
		for (int i = 0; i < conditions.length; i++)
			if (field.cardinality() > conditions[i].length) {
				enoughTurns = true;
				break;
			}
		if (!enoughTurns) return;
		//Checking for X's winning positions
		for (byte[] condition: conditions) {
			boolean win = true;
			for (byte index: condition) {
				if (field.get(index) != MARK_X) {
					win = false;
					break;
				}
			}
			if (win) {
				winX = true;
				return;
			}
		}
		//Checking for O's winning positions
		for (byte[] condition: conditions) {
			boolean win = true;
			for (byte index: condition) {
				if (field.get(index) != MARK_O) {
					win = false;
					break;
				}
			}
			if (win) {
				winO = true;
				return;
			}
		}
		//Now check if field is full - the condition for draw
		if (field.cardinality() == CELL_NUMBER) {
			winO = true;
			winX = true;
			return;
		}
	}
	
	public boolean isGameEnd() {
		return (winO || winX);
	}
	
	public String toString() {
		String string = "[";
		for (int i = 0; i < CELL_NUMBER; i++) {
			if (i % CELL_NUMBER_X == 0) string += "\r\n";
			switch(field.get(i)) {
			case MARK_NONE:
				string += '-';
				break;
			case MARK_X:
				string += 'X';
				break;
			case MARK_O:
				string += 'O';
				break;
			}
		}
		string += "\r\n]";
		return string;
	}
	
	@Override
	public boolean equals(Object arg0) {
		if (arg0.getClass() != GameField.class) return false;
		return field.toSmallest().equals(((GameField)arg0).field.toSmallest());
	}
	
	/**
	 * Produces hash code that is equal for every field that equals this. <br>
	 * (i. e. can be rotated and/or mirrored to become identical)
	 */
	public int hashCode() {
		int hash = field.toSmallest().hashCode();
		return hash;
	}
	
	private class FieldString  implements Cloneable{
		
		public FieldString() {
			bitString = new byte[3];
		}

		public int cardinality() {
			int cardinality = 0;
			for (byte b: bitString) {
				cardinality += Integer.bitCount(b);
			}
			return cardinality;
		}
		
		public FieldString clone() throws CloneNotSupportedException {
			FieldString newField = (FieldString)super.clone();
			newField.bitString = (byte[]) this.bitString.clone();
			return newField;
		}
		
		public String toString() {
			return "[" + bitString[0] + ", "  + bitString[1] + ", " + bitString[2] + "]";
		}
		
		/**
		 * @return Similar field string with minimal hash code. <br>
		 * (i. e. can be rotated and/or mirrored to become identical)
		 */
		public FieldString toSmallest() {
			FieldString smallest = this;
			for (int i = 0; i < 4; i++) {
				FieldString str = this.rotateFieldRight(i);
				if (str.hashCode() < smallest.hashCode()) smallest = str;
				str = str.mirror();
				if (str.hashCode() < smallest.hashCode()) smallest = str;
			}
			return smallest;
		}
		
		public FieldString rotateFieldRight(int n) {
			n %= 4;
			if (n == 0)
				try {
					return this.clone();
				} catch (CloneNotSupportedException e) {
					e.printStackTrace();
				}
			FieldString resultString = new FieldString();
			/* Field with following indexes:
			 * 0 1 2
			 * 3 4 5
			 * 6 7 8
			 * Rotates like that:
			 * 1:
			 * 6 3 0
			 * 7 4 1
			 * 8 5 2
			 * 2:
			 * 8 7 6
			 * 5 4 3
			 * 2 1 0
			 * 3:
			 * 2 5 8
			 * 1 4 7
			 * 0 3 6
			 */
			int[][] rotateMaps = {
					{6, 3, 0, 7, 4, 1, 8, 5, 2},
					{8, 7, 6, 5, 4, 3, 2, 1, 0},
					{2, 5, 8, 1, 4, 7, 0, 3, 6}
			};
			int[] rotateMap = rotateMaps[n - 1];
			for(int i = 0; i < 9; i++) {
				resultString.set(rotateMap[i], get(i));
			}
			return resultString;
		}
		
		/**
		 * Mirrors the field
		 * @return Mirrored cells from: <br>
		 * 0 1 2 <br>
		 * 3 4 5 <br>
		 * 6 7 8 <br>
		 * To: <br>
		 * 2 1 0 <br>
		 * 5 4 3 <br>
		 * 8 7 6
		 */
		public FieldString mirror() {
			FieldString resultString = new FieldString();
			int[] cellMirrorMapping = {2, 1, 0, 5, 4, 3, 8, 7, 6};
			for (int i = 0; i < 9; i++)
				resultString.set(cellMirrorMapping[i], get(i));
			return resultString;
		}
		
		private byte get(int i) {
			int offset = i % 3;
			int index = (i - offset) / 3;
			offset *= 2;
			byte scope = (byte) (0b11 << offset);
			byte mark = (byte) ((bitString[index] & scope) >> offset);
			return mark;
		}
		
		private void set(int i, int mark) {
			int offset = i % 3;
			int index = (i - offset) / 3;
			offset *= 2;
			byte m = (byte) (mark & 0b11);
			bitString[index] &= ~(0b11 << offset);
			bitString[index] |= m << offset;
		}
		
		public boolean equals(FieldString string) {
			for(int i = 0; i < bitString.length; i++)
				if (bitString[i] != string.bitString[i]) return false;
			return true;
		}
		
		public int hashCode() {
			int hashCode = bitString[0] + (bitString[1] << 8) + (bitString[2] << 16);
			return hashCode;
		}
		
		private byte[] bitString;
		
	}
}
